# -*- coding: utf-8 *-*
'''
@author: Geraldo Oliveira
@date: 13 de abril de 2013
@obs: 
Algoritmo de ordenacao InsertionSort
'''

class InsertionSort(object):

	def __init__(self, lista):
		'''
		Recebe a lista a ordenar

			lista  -> Lista a ordenar
		'''
		self.lista = lista

	def run(self):
		'''	
		Algoritmo InsertionSort 
		'''
		for j in xrange (1, len(self.lista)):
			key = self.lista[j]
			i = j - 1
			while i >= 0 and self.lista[i] > key:
				self.lista[i+1] = self.lista[i]
				i = i-1
				pass
			self.lista[i+1] = key

	def nome(self):
		'''
		Devolve o nome do metodo de ordenacao
		'''
		return "insertionsort"

	def o(self, n):
		'''
		Calculo do valor teorico

		Recebe:
			n 	-> numero de elementos
		'''
		return n**2

	def __str__(self):
		'''
		Imprime o objecto 
		'''
		return str(self.lista)
		